<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>排序算法的实现</title>
</head>
<body>
<script>
    function ArrayList() {

        this.array = [];

        ArrayList.prototype.size = function () {
          return this.array.length;
        };

        ArrayList.prototype.add = function (...value) {
            this.array.push(...value);
        };

        ArrayList.prototype.toString = function () {
          return this.array.join('-');
        };

        //交换array里两个值的位置
        ArrayList.prototype.swap = function (n, m) {
            const temp = this.array[n];
            this.array[n] = this.array[m];
            this.array[m] = temp;
        };

        //快速排序
        // 1.选择枢纽
        ArrayList.prototype.median = function (left, right) {
            // 1. 取出中间的位置
            const center = Math.floor((left + right) / 2);

            // 2.判断大小进行交换
            if (this.array[left] > this.array[center]) {
                this.swap(left, center);
            }
            if (this.array[center] > this.array[right])  {
                this.swap(center, right);
            }
            if (this.array[left] > this.array[center]) {
                this.swap(left, center);
            }

            // 3.将center换到 right-1 的位置
            this.swap(center, right - 1);

            return this.array[right - 1];
        };
        // 2.快速排序的实现
        ArrayList.prototype.quickSort = function () {
            this.quick(0, this.array.length - 1);
        };

        ArrayList.prototype.quick = function (left, right) {
            // 1.结束条件
            if (left >= right) return;

            // 2.获取枢纽
            let pivot = this.median(left, right);

            // 3.
            let i = left;
            let j = right -1;
            while (true) {
                while (this.array[++i] < pivot) {}
                while (this.array[--j] > pivot) {}
                if (i < j) {
                    this.swap(i, j);
                } else {
                    break;
                }
            }
            // 6.将枢纽放置在正确的位置， i的位置
            if (i !== right) {
                this.swap(i, right - 1);
            }
            // 7.分而治之
            this.quick(left, i - 1);
            this.quick(i + 1, right);
        };

        //希尔排序
        ArrayList.prototype.shellSort = function () {
            // 1.获取数组长度
            const length = this.array.length;

            // 2.初始化的增量
            let gap = Math.floor(length / 2);

            // 3.while循环(gap不断的减小)
            while (gap >= 1) {
                // 4.以gap作为间隙，进行分组，对分组进行插入排序
                for (let i = gap; i < length; i++) {
                    let temp = this.array[i];
                    let j = i;
                    while (this.array[j - gap] > temp && j >= gap) {
                        this.array[j] = this.array[j - gap];
                        j -= gap;
                    }

                    // 5.将j位置的元素赋值temp
                    this.array[j] = temp;
                }
                gap = Math.floor(gap / 2);
            }

        };

        //插入排序
        ArrayList.prototype.insertSort = function() {
            const length = this.array.length;
            let temp = 0;
            let index = 0;
            for (let i = 1; i < length; i++) {
                temp = this.array[i];
                index = i;
                while (this.array[index - 1] > temp && index > 0) {
                    this.array[index] = this.array[index - 1];
                    index--;
                }
                this.array[index] = temp;
            }
        };

        //选择排序 (测试居然发现比插入排序快)
        ArrayList.prototype.selectionSort = function () {
            const length = this.size();
            for (let i = 0; i < length; i++) {
                let min = i;
                for (let j = i + 1; j < length; j++) {
                    if (this.array[min] > this.array[j]) {
                        min = j;
                    }
                 }
                this.swap(min, i);
            }
        };

        //冒泡排序
        ArrayList.prototype.bubbleSort = function () {
            const length = this.size();
            for (let j = length - 1; j >= 0; j--) {
                for (let i = 0; i < j; i++) {
                    if (this.array[i] > this.array[i+1]) {
                        this.swap(i, i+1);
                    }
                }
            }
        };

    }

    let list = new ArrayList();
    const dataSize = 100;
    // for (let i = 1; i <= dataSize; i++) {
    //     list.array[list.array.length] = (Math.random() * dataSize) & 0xFFFFFFFF
    // }
    list.add(9, 1, 8, 2, 7, 3, 6, 4, 5);
    const start = Date.now();
    list.quickSort();

    const end = Date.now();
    console.log(end - start);

    console.log(list.toString());


    // console.log(33.15156 & 0xFFFFFFFF);
</script>
<script>
    // javascript 向数组添加元素执行效率 https://blog.csdn.net/weixin_39717194/article/details/84573525
</script>
</body>
</html>